package kmp;

/**
 * 有两个字符串a, b,从a中删除b.a剩下的字符串继续删除b,直到不能匹配删除为止，
 * 打印a剩下的部分
 */
public class DeleteAgainAndAgain {

    public static void main(String[] args) {
        s1 = "cabaababcbc".toCharArray();
        s2 = "ababc".toCharArray();
        compute();

        for (int i = 0; i < size; i++) {
            System.out.printf(String.valueOf(s1[stack1[i]]));
        }
    }

    public static char[] s1, s2;
    public static int MAXN = 100_0001;

    public static int[] next = new int[MAXN];

    public static int[] stack1 = new int[MAXN];

    public static int[] stack2 = new int[MAXN];

    public static int size;


    public static void compute() {
        size = 0;
        int n = s1.length, m = s2.length, x = 0, y = 0;
        nextArray(m);

        while (x < n) {
            if (s1[x] == s2[y]) {
                stack1[size] = x;
                stack2[size] = y;
                size++;
                x++;
                y++;
            } else if (y == 0) {
                // 母串x位置的和字串第一个字符也不相等
                // 记录母串当前位置字符
                stack1[size] = x;
                stack2[size] = -1;
                size++;
                x++;
            } else {
                // ？：向前跳到底代表什么意思
                // example: s1: "abaababc" s2: "ababc", x=3,y=3。就会跳到y=1,在跳到0的位置
                y = next[y];
            }

            if (y == m) {
                size -= m;
                y = size > 0 ? (stack2[size - 1] + 1) : 0;
            }
        }
    }

    private static void nextArray(int m) {
        next[0] = -1;
        next[1] = 0;
        int i = 2, cn = 0;

        while (i < m) {
            if (s2[i - 1] == s2[cn]) {
                next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }
    }
}
